package com.example.demo.leetcode.level2;


/**
 *
 * 用一个大小为 m x n 的二维网格 grid 表示一个箱子。你有 n 颗球。箱子的顶部和底部都是开着的。
 *
 * 箱子中的每个单元格都有一个对角线挡板，跨过单元格的两个角，可以将球导向左侧或者右侧。
 *
 * 将球导向右侧的挡板跨过左上角和右下角，在网格中用 1 表示。
 * 将球导向左侧的挡板跨过右上角和左下角，在网格中用 -1 表示。
 * 在箱子每一列的顶端各放一颗球。每颗球都可能卡在箱子里或从底部掉出来。如果球恰好卡在两块挡板之间的 "V" 形图案，或者被一块挡导向到箱子的任意一侧边上，就会卡住。
 *
 * 返回一个大小为 n 的数组 answer ，其中 answer[i] 是球放在顶部的第 i 列后从底部掉出来的那一列对应的下标，如果球卡在盒子里，则返回 -1
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/where-will-the-ball-fall
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * 输入：grid = [[1,1,1,-1,-1],[1,1,1,-1,-1],[-1,-1,-1,1,1],[1,1,1,1,-1],[-1,-1,-1,-1,-1]]
 * 输出：[1,-1,-1,-1,-1]
 *
 *
 */
public class 球会落向何处 {


    public static int[] findBall(int[][] grid) {

        int maxX = grid.length;
        int maxY = grid[0].length;
        int [] ans = new int[grid[0].length];
        for(int i = 0; i<ans.length;i++){
            ans[i] = process(0,i,maxX,maxY,grid);
        }
       return ans;
    }


    public static int process(int x,int y, int maxX, int maxY, int [][] grid){

        if(x == maxX){
            return y;
        }
        if(y<0 || y>=maxY){
            return -1;
        }
        if(grid[x][y] == 1 && (y==maxY-1 || grid[x][y+1] == -1)){
            return -1;
        }
        if(grid[x][y] == -1 && (y==0 ||  grid[x][y-1] == 1)){
            return -1;
        }

        //右移
        if(grid[x][y] == 1 && grid[x][y+1] != -1){
            return process(x+1,y+1,maxX,maxY,grid);
        }
        //左移
        if(grid[x][y] == -1 && grid[x][y-1] != 1){
            return process(x+1,y-1,maxX,maxY,grid);
        }

        return -1;
    }

    //动态规划解法
    public static int[] findBall2(int[][] grid) {

        int maxX = grid.length;
        int maxY = grid[0].length;

        int [][] dp = new int [maxX+1][maxY+1];
        for(int x=0;x<maxX+1;x++){
            dp[x][maxY] = -1;
        }
        for(int y=0;y<maxY;y++){
            dp[maxX][y] = y;
        }

        for(int x=maxX-1; x>=0;x--){
            for(int y=maxY-1;y>=0;y--){
                if(grid[x][y] == 1 && (y==maxY-1 || grid[x][y+1] == -1)){
                   dp[x][y]=-1;
                   continue;
                }
                if(grid[x][y] == -1 && (y<=0 ||  grid[x][y-1] == 1)){
                    dp[x][y]=-1;
                    continue;
                }

                //右移
                if(grid[x][y] == 1 && grid[x][y+1] != -1){
                    dp[x][y]=dp[x+1][y+1];
                    continue;
//                    return process(x+1,y+1,maxX,maxY,grid);
                }
                //左移
                if(grid[x][y] == -1 && grid[x][y-1] != 1){
                    dp[x][y]=dp[x+1][y-1];
                    continue;
//                    return process(x+1,y-1,maxX,maxY,grid);
                }

            }
        }

        int [] ans = new int[dp[0].length-1];
        for(int i =0 ;i<ans.length;i++){
            ans[i]=dp[0][i];
        }
        return ans;
    }



    public static void main(String[] args) {
        int [][] grid = {{1,1,1,1,1,1},{-1,-1,-1,-1,-1,-1},{1,1,1,1,1,1},{-1,-1,-1,-1,-1,-1}};
        int[] ball = findBall(grid);
        for(int i=0;i<ball.length;i++){
            System.out.println(ball[i]);
        }
        int[] ball2 = findBall2(grid);
        for(int i=0;i<ball2.length;i++){
            System.out.println(ball2[i]);
        }
    }



}
